1. Field of the Invention
This invention relates to method and apparatus for providing a multiply redundant RAID system.
2. Description of the Related Art
RAID (Redundant Array of Independent Disks) is a data storage system that employs two or more disk drives (or storage devices in general) and delivers fault tolerance and performance. RAID architectures that can tolerate multiple disk failures (i.e. multiply redundant) are known. One such system is described in Wiencko et al., “Data Redundancy Methods and Apparatus”, U.S. Pat. No. 6,557,123, filed 2 Aug. 1999, issued 29 Apr. 2003, assigned to the assignee of the present disclosure, which describes a method for encoding data that protects against simultaneous m disk failures in an array of n disks, as well as a code discovery method. Other methods for double- or triple-disk failure protection are also known; one category of such methods uses Reed-Solomon or Reed-Solomon-like codes.
Reed-Solomon (R-S) error correction is a coding scheme which works by first constructing a polynomial from the data symbols to be transmitted and then sending an over-sampled plot of the polynomial instead of the original symbols. (See Wikipedia: “Reed-Solomon error correction”, http://en.wikipedia.org/wiki/Reed-Solomon_error_correction.) Thus, a matrix for a massively over-sampling R-S on two symbols (matrix on the right notation and linear polynomials) would be
                              code          ⁡                      (                          (              xy              )                        )                          =                              (            xy            )                    ⁢                      (                                                            1                                                  1                                                  1                                                                                                                                          1                                                                                                                                                                                                                                                                                                                                                      ⋯                                                                                                                                                                      α                                                  β                                                  γ                                                                                                                                          χ                                                      )                                              (        1        )            where α, β, γ, . . . χ are n distinct values in some finite field. If α is primitive and a generator of the multiplicative group, and the number of coded values (matrix columns) is less than the order of the field, then one may haveβ=α2γ=α3and so forth: this leads to straightforward algorithms (Berlekamp) for solving for errors. The coding of (1) is called “non-systematic” because nowhere among the entries to code((x y)) do x or y themselves necessarily appear. To get a systematic code, one for which the data appears in clear form among the coded values, one may multiply the matrix on the left by a 2×2 matrix that forces the left two columns to an identity matrix. But then, there is no simple expression for the matrix entries.
The above example has only two data points and n−2 parities. To increase the data dimension, add rows raising α, β, γ, . . . to consecutive powers, and use Vandermonde. Realistic cases will sample n times in a polynomial of degree n−m−1, where m is comparatively small (perhaps 2 or 3) and n large (perhaps 15 or larger). This makes the solution expression more complicated, if a systematic code is desired.
A variant, which only needs to be mentioned here, is that found in Murthy et al., “Multiple Drive Failure Recovery for a Computer System having an Array of Storage Drives”, U.S. Pat. No. 6,694,479. This uses a matrix like that found in (1), but as an implicit condition, requiring multiplication with a data/parity vector on the right of the matrix to give zero. For this variant, the data dimension would be n−2 and the parity dimension 2. It is easily extended (by Vandermonde) to parity greater than 2 by adding rows raising α, β, γ, . . . to consecutive powers. This amounts to a “dual” form of standard Reed-Solomon.
Another algorithm has also been called “Reed-Solomon” (in Blaum et al., “EVENODD: An Optimal Scheme for Tolerating Double Disk Failures in RAID Architectures”, IEEE, 1994, pp 245–254, 1063–6897/94, hereinafter [B2]), or “B-adjacent” (in Blaum et al., “Method and Means for B-Adjacent Coding and Rebuilding Data from up to Two Unavailable DASDs in a DASD Array”, U.S. Pat. No. 5,333,143, hereinafter [B1]). It places the matrix like that found in (1) below an identity matrix and uses it to multiply by a data vector on the right, expressed as equation (2) below. This automatically gets a systematic code if it works. But Vandermonde, by itself, does not prove it works.
                              code          ⁡                      (                          (                                                                    x                                                                                        y                                                                                        ⋮                                                                                        z                                                              )                        )                          =                                            (                                                                    1                                                        0                                                        ·                                                        ·                                                        0                                                                                        0                                                        1                                                        ·                                                        ·                                                        0                                                                                        ·                                                        ·                                                        ·                                                        ·                                                        ·                                                                                        ·                                                        ·                                                        ·                                                        ·                                                        ·                                                                                        0                                                        0                                                        ·                                                        ·                                                        1                                                                                        ζ                                                        η                                                        ·                                                        ·                                                        θ                                                                                        ·                                                        ·                                                        ·                                                        ·                                                        ·                                                              )                        ⁢                          (                                                                    x                                                                                        y                                                                                        ⋮                                                                                        z                                                              )                                =                                    (                                                                    I                                                                                        P                                                              )                        ⁢                          (                                                                    x                                                                                        y                                                                                        ⋮                                                                                        z                                                              )                                                          (        2        )            Here I is an identity matrix, and the parity matrix P has horizontal dimension equal to the vector to be encoded, and vertical dimension equal to the parity count (dimension of code vector minus dimension of vector that was encoded).
The requirement for a non-systematic expression of the form of (1) to give an erasure code, where any surviving set of code values of the count of the data values can be decoded, is for all square submatrices of maximal size of the matrix in (1) to be invertible. This is obvious in the case of equation (1) because they are Vandermonde.
The requirement for a systematic expression of the form of (2) to give an erasure code, where any surviving set of code values of the count of the data values can be decoded, is for all square submatrices of the parity matrix P to be invertible. This does not follow in general if maximal submatrices are Vandermonde.
However, if P in (2) is set equal to the row dimension 2 matrix in (1), and we require that α, β, . . . be unequal and nonzero, then the stronger requirement that all square submatrices be invertible is satisfied. Namely, one just needs to prove it for 1×1 square submatrices, which are invertible if nonzero. This is the approach used in [B1] to obtain a redundancy 2 code. This Reed-Solomon-based method has sometimes been referred to as “RAID6”. It is also the code used in [B2] as a foil to Evenodd, and in [B2] it is called “Reed-Solomon”. In the present disclosure it is referred to as “Reed-Solomon-like”.